`
https://leetcode.cn/problems/heaters/
`

/**
 * @param {number[]} houses
 * @param {number[]} heaters
 * @return {number}
 */
var findRadius = function (houses, heaters) {
  const n = houses.length, m = heaters.length
  houses.sort((a, b) => a - b)
  heaters.sort((a, b) => a - b)

  // 半径为 r ，能否供暖所有房屋
  const check = (r) => {
    for (const h of houses) {
      // 找到第一个可能覆盖到当前房子的位置
      const j = _.sortedIndex(heaters, h - r)
      // while (j < m && h > heaters[j] + r) j++;
      // 确定是否能覆盖到
      if (j < m && h >= heaters[j] - r && h <= heaters[j] + r) continue
      return false
    }
    return true
  }

  // 加热半径为 -1 没有任何房屋能被供暖
  let left = -1
  // 加热半径设置为距离最远的房屋和供暖之间的距离，肯定能保证全部能被供暖
  let right = Math.max(
    Math.abs(houses.at(-1) - heaters[0]),
    Math.abs(heaters.at(-1) - houses[0])
  )

  while (left + 1 < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (check(mid)) {
      right = mid
    } else {
      left = mid
    }
  }
  return right
};